import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
// https://leetcode.cn/problems/letter-combinations-of-a-phone-number
public class LetterCombinations {
    static class Solution {

        private static HashMap<Character,List<Character>> dict = new HashMap<>();
        static{
            dict.put('2',new ArrayList<>(Arrays.asList('a','b','c')));
            dict.put('3',new ArrayList<>(Arrays.asList('d','e','f')));
            dict.put('4',new ArrayList<>(Arrays.asList('g','h','i')));
            dict.put('5',new ArrayList<>(Arrays.asList('j','k','l')));
            dict.put('6',new ArrayList<>(Arrays.asList('m','n','o')));
            dict.put('7',new ArrayList<>(Arrays.asList('p','q','r','s')));
            dict.put('8',new ArrayList<>(Arrays.asList('t','u','v')));
            dict.put('9',new ArrayList<>(Arrays.asList('w','x','y','z')));


        }

        private List<String> res = new ArrayList<>();
        public List<String> letterCombinations(String digits) {


            if(digits.length() == 0 ) return res;
            backtracking(new ArrayList<>(),digits,0);
            return res;

        }
        private void backtracking(List<Character> path, String digits , int  level)
        {
            if(path.size() == digits.length())
            {
                StringBuilder sb = new StringBuilder();
                for(char c : path)
                {
                    sb.append(c);
                }
                res.add(sb.toString());
                return;
            }
            char ch = digits.charAt(level);
            List<Character> list = dict.get(ch);
            for(int i = 0; i <list.size();i ++)
            {
                path.add(list.get(i));
                backtracking(path,digits,level + 1);
                path.remove(path.size()-1);
            }
        }
    }
}
